package com.code.leetcode.DP;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/7/30 9:23
 */
public class _2_The1139 {
    public int largest1BorderedSquare(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        // 利用动态规划将每个点的左边最长和上边最长表示出来
        int[][][] dp = new int[m + 1][n + 1][2];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (grid[i - 1][j - 1] == 1) {
                    dp[i][j][0] = 1 + dp[i][j - 1][0];
                    dp[i][j][1] = 1 + dp[i - 1][j][1];
                }
            }
        }

        int res = 0;
        // 通过遍历每个点的最小长度是不是也被别的视为最大长度，如果认为还要长，则最小长度减一尝试
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int side = Math.min(dp[i][j][0], dp[i][j][1]); side >= 1; side--) {
                    if (dp[i][j - side + 1][1] >= side && dp[i - side + 1][j][0] >= side) {
                        res = Math.max(res, side);
                        // 因为是逐步递减，只要找到一个最大符合条件的就行
                        break;
                    }
                }
            }
        }
        return res * res;
    }
}
